123. Best Time to Buy and Sell Stock III

Hard

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1
2
3

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

改良版brute force。一维dp list 用来存储一次交易的最大利润。first_idx list存储第一次交易结束时间点，first_max存储第一次交易，ans存两次交易最大值。每次遍历搜索每次潜在的第一次交易结束时间，进行比较，存储结果。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        ans = 0
        dp = [0] * len(prices)
        first_idx = [] 
        first_max = 0
        
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                for j in first_idx:
                    second = prices[i] - min(prices[j:i])
                    ans = max(ans, dp[j] + second)
                
                if (prices[i] - min(prices[:i])) > first_max:
                    first_max = prices[i] - min(prices[:i])
                    dp[i] = prices[i] - min(prices[:i])
                    first_idx.append(i)
                else:
                    dp[i] = first_max
                
            else:
                dp[i] = dp[i-1]
        # print(dp)
        return max(ans, first_max)

2.使用局部和全局两个dp list

最近在刷动态规划的题，这篇文章是我写的动态规划一点想法，和大家分享一下

以及这题的参考

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int[] g = new int[3];
        int[] l = new int[3];
        for(int i = 0; i < prices.length - 1; i++){
            int diff = prices[i+1] - prices[i];
            for(int j = 2; j >= 1; j--){
                l[j] = Math.max(g[j-1] + Math.max(0, diff), l[j]+diff);
                g[j] = Math.max(g[j], l[j]);
            }
        }
        return g[2];
    }
}

Syntax:

最大值。Math.max。大写
new的用法